package leecode

import "math"

func smallestRange(nums [][]int) (result []int) {
	//将列表中的所有数映射到hash表中 key为数组中的元素 , value为对应元素所在的组
	hashMap := make(map[int][]int)
	minVal, maxVal := math.MinInt, math.MaxInt
	for i, list := range nums {
		for _, x := range list {
			hashMap[x] = append(hashMap[x], i)
			minVal = min(minVal, x)
			maxVal = max(maxVal, x)
		}
	}
	// 滑动窗口从最小值开始华东
	left, right := minVal, maxVal
	memo := make([]int, len(nums)) //记录每个列表中包含的数的个数
	need := 0                      //记录满足条件的数的个数
	bestL, bestR := minVal, maxVal //记录最小区间的起始和结束位置
	for right <= maxVal {
		//如果right在map中存在
		if indexes, ok := hashMap[right]; ok {
			for _, idx := range indexes {
				//记录区间满足了第idx个列表
				memo[idx]++
				if memo[idx] == 1 {
					need++
				}
			}
		}
		//当所有列表都满足了 , 记录区间大小,并缩小窗口
		for need == len(nums) {
			// 缩小区间
			if right-left < bestR-bestL {
				bestL = left
				bestR = right
			}
			// 移动左边界
			if indexs, ok := hashMap[left]; ok {
				for _, idx := range indexs {
					if memo[idx] == 1 {
						need--
					}
					memo[idx]--
				}
			}
			left++
		}
		right++
	}
	return []int{bestL, bestR}
}
